package com.zlp.partice;

import org.junit.Test;

import javax.swing.tree.TreeNode;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @Author: zhulaiping
 * @Date: 2021/7/22 9:38
 */
public class Day20210722 {

    Map<Integer, Integer> map = new HashMap<>();
    int ret = 0;
    public int widthOfBinaryTree(TreeNode root) {
        dfs5(root,1,1);
        return ret;
    }

    private void dfs5(TreeNode root, int i,int depth) {
        if(root==null) return;
        if(map.containsKey(depth)){
            map.put(depth,i);
        }
        ret = Math.max(ret,i-map.get(depth)+1);
        dfs5(root.left,i*2,depth+1);
        dfs5(root.right,i*2+1,depth+1);
    }

    public int[] shuffle(int[] nums, int n) {
        int[] ret = new int[n * 2];
        int l = 0, r = n;
        for (int i = 0; i < 2*n; i += 2) {
            ret[i] = nums[l++];
            ret[i + 1] = nums[r++];
        }
        return ret;
    }

    @Test
    public void ee(){
        System.out.println(getDate(2));
        System.out.println(getDate(3));
    }
    private Date getDate(int n) {
        Calendar instance = Calendar.getInstance();
        instance.setTime(new Date());
        instance.add(Calendar.DAY_OF_MONTH, n);
        return instance.getTime();
    }

    class Node {
        int val;
        Node next;
        Node random;
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node root = new Node(0);
        Node temp = root,temp2 = head;
        while (head!=null){
            Node node = new Node(head.val);
            temp.next = node;
            map.put(head,node);
            temp = node;
            head = head.next;
        }
        temp = root.next;
        while (temp2!=null){
            temp.random = map.get(temp2.random);
            temp = temp.next;
            temp2 = temp2.next;
        }
        return root.next;
    }
    public boolean isCovered(int[][] ranges, int left, int right) {
        Arrays.sort(ranges,(o1, o2) -> o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);
        for (int[] arr:ranges){
            if(left>=arr[0]&&left<=arr[1]){
                left = arr[1]+1;
            }
            if(left>=right) return true;
        }
        return false;
    }

    public String maximumTime(String time) {
        StringBuilder ret = new StringBuilder();
        char c1 = time.charAt(0);
        char c2 = time.charAt(1);
        char c3 = time.charAt(3);
        char c4 = time.charAt(4);
        ret.append(c1!='?'?c1:(c2=='?'||c2<'4'?'2':'1'));
        ret.append(c2!='?'?c2:(ret.charAt(0)=='2'?'3':'9'));
        ret.append(':');
        ret.append(c3!='?'?c3:'5');
        ret.append(c4!='?'?c4:'9');
        return ret.toString();
    }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
    }


    int value;


    private void dfs(TreeNode root) {
        if(root==null) return;
        if(root.val>value&&ret>root.val){
            ret = root.val;
        }
        dfs(root.left);
        dfs(root.right);
    }
    Set<TreeNode> set;




    public List<List<Integer>> verticalTraversal(TreeNode root) {
        TreeMap<Integer,TreeMap<Integer,List<Integer>>>map = new TreeMap<>();
        dfs3(root,0,0,map);
        List<List<Integer>>ret = new ArrayList<>();
        for (TreeMap<Integer,List<Integer>> map1:map.values()){
            List<Integer> curList = new ArrayList<>();
            for (List<Integer>list:map1.values()){
                Collections.sort(list);
                curList.addAll(list);
            }
            ret.add(curList);
        }
        return ret;
    }

    private void dfs3(TreeNode root, int x, int y,TreeMap<Integer, TreeMap<Integer,List<Integer>>>map) {
        if(root==null) return;
        TreeMap<Integer, List<Integer>> map1 = map.getOrDefault(x, new TreeMap<>());
        List<Integer> list = map1.getOrDefault(y, new ArrayList<>());
        list.add(root.val);
        map1.put(y,list);
        map.put(x,map1);
        dfs3(root,x-1,y+1,map);
        dfs3(root,x+1,y+1,map);
    }
    @Test
    public void oo(){
        /*kWeakestRows(new int[][]{{1,1,0,0,0},
                {1,1,1,1,0},
                {1,0,0,0,0},
                {1,1,0,0,0},
                {1,1,1,1,1}},3);*/
        int a = -5%5;
        System.out.println(a);
        arrayRankTransform(new int[]{37,12,28,9,100,56,80,5,12});
    }
    public int[] arrayRankTransform(int[] arr) {
        int[] temp = new int[arr.length],ret = new int[arr.length];
        System.arraycopy(arr,0,temp,0,arr.length);
        Arrays.sort(temp);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0;i<temp.length;i++) {
            map.put(temp[i],map.getOrDefault(temp[i],map.size()+1));
        }
        for (int i=0;i<arr.length;i++){
            ret[i] = map.get(arr[i]);
        }
        return ret;
    }
    public int[] kWeakestRows(int[][] mat, int k) {
        int row = mat.length;
        int[] ret = new int[k];
        int[][] map = new int[row][2];
        for (int i=0;i<row;i++) {
            int cur = 0;
            for (int arr : mat[i]) {
                if(arr==0)break;
                cur+=arr;
            }
            map[i][0] = i;
            map[i][1] = cur;
        }
        Arrays.sort(map,(o1, o2) -> o1[1]!=o2[1]?o1[1]-o2[1]:o1[0]-o2[0]);
        for (int i=0;i<k;i++){
            ret[i] = map[i][0];
        }
       return ret;
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        int INF = Integer.MAX_VALUE/2;
        int[] ret = new int[n];
        Arrays.fill(ret,INF);
        boolean[] visited = new boolean[n];
        int[][] g = new int[n][n];
        for (int i=0;i<n;i++){
            Arrays.fill(g[i],INF);
        }
        for (int[] cur:times){
            int x = cur[0]-1,y = cur[1]-1;
            g[x][y] = cur[2];
        }
        int cur = k-1;
        ret[cur] = 0;
        for (int j=0;j<n;j++){
            int min = INF;
           for (int i=0;i<n;i++){
               if(!visited[i]&&ret[i]<min){
                   min = ret[i];
                   cur = i;
               }
           }
           visited[cur] = true;
           for (int i=0;i<n;i++){
               ret[i] = Math.min(ret[i],ret[cur]+g[cur][i]);
           }
        }
        int result = Arrays.stream(ret).max().getAsInt();
        return result==Integer.MAX_VALUE?-1:result;
    }


    public List<Integer> eventualSafeNodes(int[][] graph) {
        int len = graph.length;
        int[] map = new int[len];
        List<Integer> ret = new ArrayList<>();
        for (int i=0;i<len;i++){
            if(dfs4(i,map,graph)){
                ret.add(i);
            }
        }
        return ret;
    }
    private boolean dfs4(int i, int[] map, int[][] graph) {
        if(map[i]>0){
            return map[i]==2;
        }
        map[i] = 1;
        for (int index:graph[i]){
            if(!dfs4(index,map,graph))
                return false;
        }
        map[i] = 2;
        return true;
    }
    public int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        int[] ret = new int[n];
        ret[0] = 0;ret[1] = 1;ret[2] = 1;
        for (int i=3;i<=n;i++){
            ret[i] = ret[i-1]+ret[i-2]+ret[i-3];
        }
        return ret[n-1];
    }
    public boolean circularArrayLoop(int[] nums) {
        int index=0,len = nums.length;
        for (int i=0;i<len;i++){
            index =(index+nums[index]+len)%len;
            if(index==0) return true;
        }
        return false;
    }
    public int nthSuperUglyNumber(int n, int[] primes) {
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.add(1L);
        Long poll = 1L;
        for(int i=0;i<n;i++){
            poll = queue.poll();
            for (int v:primes){
                if(!set.contains(v*poll)){
                    set.add(v*poll);
                    queue.add(v*poll);
                }
            }
        }
        return poll.intValue();
    }

    public int numberOfArithmeticSlices(int[] nums) {
        int len = nums.length,ret = 0;
        if(len<3) return 0;
        int v = nums[1]-nums[0],cnt = 0;
        for (int i=2;i<len;i++){
            if(nums[i]-nums[i-1]==v){
               ++cnt;
            }else {
               cnt = 0;
               v = nums[i]-nums[i-1];
            }
            ret += cnt;
        }
        return ret;
    }

    @Test
    public void ss(){
        //numberOfArithmeticSlices(new int[]{1,2,3,8,9,10});
        validSquare(new int[]{0,0},new int[]{13,0},new int[]{5,12},new int[]{18,12});
    }
    public long len(int[] p1,int[] p2){
        return (p2[0]-p1[0])*(p2[0]-p1[0]) + (p2[1]-p1[1])*(p2[1]-p1[1]);
    }
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        if(p1[0]==p2[0]&&p1[1]==p2[1] ||
                p1[0]==p3[0]&&p1[1]==p3[1] ||
                p1[0]==p4[0]&&p1[1]==p4[1] ||
                p2[0]==p3[0]&&p2[1]==p3[1] ||
                p2[0]==p4[0]&&p2[1]==p4[1] ||
                p3[0]==p4[0]&&p3[1]==p4[1]){
            return false;
        }
        long[] l = new long[6];
        l[0] = len(p1,p2);
        l[1] = len(p1,p3);
        l[2] = len(p1,p4);
        l[3] = len(p3,p2);
        l[4] = len(p4,p3);
        l[5] = len(p2,p4);
        Arrays.sort(l);
        return l[0] == l[1] && l[0] == l[2] && l[0] == l[3] && l[4] == l[5];
    }
    public int maxLevelSum(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int level = 0,ret = 0,max = Integer.MIN_VALUE;
        while (!queue.isEmpty()){
            level++;
            int cnt = queue.size();
            int cur = 0;
            for (int i=0;i<cnt;i++){
                TreeNode poll = queue.poll();
                if(poll.left!=null) queue.offer(poll.left);
                if(poll.right!=null) queue.offer(poll.right);
                cur += poll.val;
            }
            if(cur>max){
                max = cur;
                ret = level;
            }
        }
        return ret;
    }

    public String generateTheString(int n) {
        char a = 'a',b = 'b';
        char[] ret = new char[n];
        for (int i=0;i<n-1;i++){
            ret[i] = a;
        }
        ret[n-1] = n%2==1?a:b;
        return new String(ret);
    }

    class MyCircularQueue {

        private int[] arr;
        int head = 0,tail = 0,cur = 0;

        public MyCircularQueue(int k) {
            arr = new int[k];
        }

        public boolean enQueue(int value) {
            if (isFull()) return false;
            cur++;
            arr[tail] = value;
            tail = (tail + 1) % arr.length;
            return true;
        }

        public boolean deQueue() {
            if(isEmpty()) return false;
            cur--;
            head = (head+1)%arr.length;
            return true;
        }

        public int Front() {
            if(isEmpty()) return -1;
            return arr[head];
        }

        public int Rear() {
            if(isEmpty()) return -1;
            return arr[tail-1];
        }

        public boolean isEmpty() {
            return cur == 0;
        }

        public boolean isFull() {
            return cur == arr.length;
        }
    }

    public List<Integer> minSubsequence(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        int sum = Arrays.stream(nums).sum();
        int cur = 0;
        for (int i=nums.length-1;i>=0;i--){
            list.add(nums[i]);
            cur+=nums[i];
            sum -= nums[i];
            if(cur>sum) break;
        }
        return list;
    }

    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if(depth == 1){
            TreeNode cur = new TreeNode(val);
            cur.left = root;
            return cur;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int level = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i=0;i<size;i++){
                TreeNode cur = queue.poll();
                if(level == depth-1){
                    TreeNode leftNode = new TreeNode(val);
                    leftNode.left = cur.left;
                    cur.left = leftNode;
                    TreeNode rightNode = new TreeNode(val);
                    rightNode.right = cur.right;
                    cur.right = rightNode;
                }else {
                    if(cur.left!=null) queue.offer(cur.left);
                    if(cur.right!=null) queue.offer(cur.right);
                }
            }
            if(level == depth-1) break;
            level++;
        }
        return root;
    }

    @Test
    public void ll(){
        //stringMatching(new String[]{"leetcode","et","code"});
        exclusiveTime(8,Arrays.asList("0:start:0","1:start:5","2:start:6","3:start:9","4:start:11","5:start:12","6:start:14","7:start:15","1:start:24","1:end:29","7:end:34","6:end:37","5:end:39","4:end:40","3:end:45","0:start:49","0:end:54","5:start:55","5:end:59","4:start:63","4:end:66","2:start:69","2:end:70","2:start:74","6:start:78","0:start:79","0:end:80","6:end:85","1:start:89","1:end:93","2:end:96","2:end:100","1:end:102","2:start:105","2:end:109","0:end:114"));
    }

    public int[] exclusiveTime(int n, List<String> logs) {
        int[] ret = new int[n];
        LinkedList<String>stack = new LinkedList<>();
        for (int i=0;i<logs.size();i++){
            String log = logs.get(i);
            if(log.charAt(2)=='s') stack.push(log);
            else {
                String[] logArr = log.split(":");
                String pop = stack.pop();
                String[] popArr = pop.split(":");
                int val = Integer.parseInt(logArr[2])-Integer.parseInt(popArr[2])+1;
                ret[Integer.parseInt(logArr[0])] += val;
                if(!stack.isEmpty()){
                    ret[Integer.parseInt(stack.peek().split(":")[0])] -= val;
                }

            }
        }
        return ret;
    }

    public List<String> stringMatching(String[] words) {
        Set<String> ret = new HashSet<>();
        for (int i=0;i<words.length;i++){
            for (int j=0;j<words.length;j++){
                if(i==j) continue;
                if(isSubString(words[i],words[j])){
                    ret.add(words[j]);
                }
            }
        }
        return new ArrayList<>(ret);
    }

    private boolean isSubString(String word, String word1) {
        if(word.length()<=word1.length()) return false;
        char[] chars = word.toCharArray();
        char[] chars1 = word1.toCharArray();
        for (int i=0;i<chars.length;i++){
            if(chars.length-i+1<chars1.length) break;
            if(chars[i] == chars1[0]){
                int j = 0,index = i;
                while (j<chars1.length&&chars[index]==chars1[j]){
                    index++;
                    j++;
                }
                if(j == chars1.length) return true;
            }
        }
        return false;
    }

    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        if(root.val<val){
            TreeNode cur = new TreeNode(val);
            return cur.left = root;
        }
        root.right = insertIntoMaxTree(root.right,val);
        return root;
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        int index = 0;
        for (int i=0;i< pushed.length;i++){
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[index]){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }

}
